/**
 * 
 */
package net.sf.graph4j.algorithm.graph.maxflow;


import java.util.HashMap;
import java.util.List;
import java.util.Map;

import net.sf.graph4j.element.IConstants;
import net.sf.graph4j.element.graph.Edge;
import net.sf.graph4j.element.graph.Graph;
import net.sf.graph4j.element.graph.GraphFactory;
import net.sf.graph4j.element.graph.Vertex;

/**
 * @author palomino
 *
 */
public class FlowDescriptor implements IConstants{

	private Graph g;
	
	private Map<Vertex, Vertex> vertexOrigion2Residual = new HashMap<Vertex, Vertex>();
	
	private Map<Edge, Edge> edgeResidual2Origion = new HashMap<Edge, Edge>();
	
	private Map<Edge, Edge> cisEdgeOrigion2Residual = new HashMap<Edge, Edge>();
	
	private Map<Edge, Edge> transEdgeOrigion2Residual = new HashMap<Edge, Edge>();
	
	private GraphFactory factory = new GraphFactory();

//	private Map<VertexPair, Double> flowMap = new HashMap<VertexPair, Double>();
	
	/**
	 * @param g
	 * @param source
	 * @param sink
	 */
	public FlowDescriptor(Graph g) {
		super();
		// TODO Auto-generated constructor stub
		this.g = g;

		initFlow();
		initResidualGraph();
	}

	private void initFlow() {
		// TODO Auto-generated method stub
		for (Edge edge : g.getEdges()) {
//			putValue(edge.getSource(), edge.getTarget(), 0.0);
//			putValue(edge.getTarget(), edge.getSource(), 0.0);
			
			edge.putProperty(PropertyFlow, 0.0);
		}
	}
	
	private Graph residualGraph;
	
	/**
	 * @return Returns the residualGraph.
	 */
	public Graph getResidualGraph() {
		return residualGraph;
	}

	private Graph initResidualGraph (){
		
		residualGraph = factory.produceGraph(Directed.True, Weighted.True);
			
		for (Vertex v : g.getVertices()) {
			try {
				Vertex newV = v.clone();
				residualGraph.addVertex(newV);
				vertexOrigion2Residual.put(v, newV);
			} catch (CloneNotSupportedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		
		refreshResidualGraph();
		
		return residualGraph;
	}
	
	public void augment(List<Edge> path, double value) {
		// TODO Auto-generated method stub
		for (Edge edge : path) {
			increaseValue (map(edge), value * (Integer)edge.getProperty(PropertyTag));
		}
		
		refreshResidualGraph();
	}

	private void increaseValue(Edge edge, double value) {
		// TODO Auto-generated method stub
		edge.putProperty(PropertyFlow, (Double)edge.getProperty(PropertyFlow) + value);
	}

	public void refreshResidualGraph() {
		// TODO Auto-generated method stub
		
		factory.removeAllEdge(residualGraph);
		edgeResidual2Origion.clear();
		cisEdgeOrigion2Residual.clear();
		transEdgeOrigion2Residual.clear();
		
		for (Edge e : g.getEdges()) {
			if (residualGraph.getEdgeByVertex(map(e.getSource()), map(e.getTarget())) == null){
				
				double residual = e.getWeight() - (Double)e.getProperty(PropertyFlow);
								
				Edge reverseE = g.getReverseEdge(e);
				if (reverseE != null)
					residual += (Double)reverseE.getProperty(PropertyFlow);
				
				if (residual > 0) {
					Edge newEdge = factory.produceEdge(residualGraph, map(e.getSource()), map(e.getTarget()), residual);
					newEdge.putProperty(PropertyTag, 1);
					edgeResidual2Origion.put(newEdge, e);
					cisEdgeOrigion2Residual.put(e, newEdge);
				}
				
				//reverse edge
				double reverseResidual = (Double)e.getProperty(PropertyFlow);
				if (reverseE != null)
					reverseResidual += reverseE.getWeight() - (Double)reverseE.getProperty(PropertyFlow);
				
				if (reverseResidual > 0) {
					Edge newEdge = factory.produceEdge(residualGraph, map(e.getTarget()), map(e.getSource()), reverseResidual);
					newEdge.putProperty(PropertyTag, -1);
					edgeResidual2Origion.put(newEdge, e);
					transEdgeOrigion2Residual.put(e, newEdge);
				}
			}
		}
	}
	
	public Vertex map (Vertex v) {
		return vertexOrigion2Residual.get(v);
	}
	
	public Edge map (Edge e) {
		return edgeResidual2Origion.get(e);
	}

	public Edge getCisResidualEdge(Edge e) {
		// TODO Auto-generated method stub
		return cisEdgeOrigion2Residual.get(e);
	}
	
	public Edge getTransResidualEdge(Edge e) {
		// TODO Auto-generated method stub
		return transEdgeOrigion2Residual.get(e);
	}

	/* (non-Javadoc)
	 * @see java.util.Map#containsKey(java.lang.Object)
	 */
//	public boolean containsKey(Vertex source, Vertex target) {
//		return flowMap.containsKey(new VertexPair(source, target));
//	}

	/* (non-Javadoc)
	 * @see java.util.Map#get(java.lang.Object)
	 */
//	public double getValue(Vertex source, Vertex target) {
//		return flowMap.get(new VertexPair(source, target));
//	}

	/* (non-Javadoc)
	 * @see java.util.Map#put(K, V)
	 */
//	public double putValue(Vertex source, Vertex target, Double value) {
//		return flowMap.put(new VertexPair(source, target), value);
//	}
	
//	public double increaseValue (Vertex source, Vertex target, Double value) {
//		if (containsKey(source, target)) {
//			double newValue = getValue(source, target) + value;
//			putValue(source, target, newValue);
//			return newValue;
//		}
//		else {
//			putValue(source, target, value);
//			return value;
//		}
//	}
}
